package or;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class T2585 {

    private static final int MOD = (int) 1e9 + 7;
    public int waysToReachTarget(int target, int[][] types) {
        int[][] f = new int[target + 1][types.length];
        for(int []type:f){
            Arrays.fill(type,-1);
        }
        f[0][0] = 1;
        return num(target, types.length - 1, types,f);
    }

    public int num(int target, int i, int[][] types,int[][]f) {
        if (target == 0) return 1;
        if (target < 0 || i < 0) return 0;
        if(f[target][i]!=-1)return f[target][i];

        int sum = 0;
        int j = 0;
        while (j <= types[i][0]) {
            int targetS = target - types[i][1] * j;
            if (targetS < 0) break;
            sum =(sum+ num(targetS, i - 1, types,f))% MOD;
//            System.out.println(targetS + "   " + (i - 1) + "   " + sum);
            j++;
        }
        f[target][i]=sum;
        return sum;
    }


//6
//        [[6,1],[3,2],[2,3]]


    @Test
    public void test() {
        int[][] ints = {{6, 1}, {3, 2}, {2, 3}};
        int re = waysToReachTarget(6, ints);
        System.out.println(re);

    }


}
